#define _CRT_SECURE_NO_WARNINGS 1


#include<vector>
#include<iostream>

using namespace std;

void _MergeSort(vector<int>& v, int left, int right, vector<int>& temp)
{
	if (left >= right)
	{
		return;
	}
	int mid = (left + right) / 2;
	_MergeSort(v, left, mid, temp);
	_MergeSort(v, mid + 1, right, temp);
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (v[begin1] < v[begin2])
		{
			temp[index++] = v[begin1++];
		}
		else
		{
			temp[index++] = v[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		temp[index++] = v[begin1++];
	}
	while (begin2 <= end2)
	{
		temp[index++] = v[begin2++];
	}
	for (int i = left; i <= right; i++)
	{
		v[i] = temp[i];
	}
}

void MergeSort(vector<int>& v, int n)
{
	vector<int> temp(n);
	_MergeSort(v, 0, n - 1, temp);
}

vector<int> sortArray(vector<int>& nums)
{
	MergeSort(nums, nums.size());
	return nums;
}

int main()
{
	vector<int> v = { 5,2,3,1 };
	vector<int> ret = sortArray(v);
	for (auto& e : ret)
	{
		cout << e << ' ';
	}
	cout << endl;

	return 0;
}